from Q9 import Timer,IntGenerator
from lib import quick

def three_sampling(func):
    def inner(lst):
        top=lst[0]
        mid=lst[len(lst)//2]
        end=lst[-1]
        if min(top,end)<mid<max(top,end):
            lst[0],lst[len(lst)//2]=lst[len(lst)//2],lst[0]
        elif min(top,mid)<end<max(top,mid):
            lst[0],lst[-1]=lst[-1],lst[0]
        return func(lst)
    return inner

@Timer("Three point sampling")
@three_sampling
def quick_TS(lst):
    return quick(lst)

@Timer("First point sampling")
def quick_FS(lst):
    return quick(lst)

if __name__ == "__main__":
    n = 1000
    lst = [i for i in IntGenerator(n)]
    lst1=quick_FS(lst)
    lst2=quick_TS(lst)
    if lst1==lst2==sorted(lst):
        print("All pass")
    else:
        print("error")
